package Lee_code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 请你设计并实现一个满足
 * LRU (最近最少使用) 缓存 约束的数据结构。
 */
class Lee_146_1024 {

    HashMap<Integer, Integer> hashMap;
    int totalSize;
    List<Integer> seen;

    public Lee_146_1024(int capacity) {
        seen = new ArrayList<>();
        hashMap = new HashMap<>(capacity);
        totalSize = capacity;
    }

    public int get(int key) {
        if (seen.contains(key)) {
            seen.remove((Integer) key);
        }
        seen.add(key);

        if (hashMap.containsKey(key)) {
            return hashMap.get(key);
        }
        return -1;
    }

    public void put(int key, int value) {
        if (hashMap.containsKey(key)) {
            hashMap.put(key, value);
        } else {
            if (hashMap.size() == totalSize) {
                // 逐出最不常用的
                int index = seen.get(0);
                hashMap.remove(index);
            } else {
                hashMap.put(key, value);
                seen.add(key);
            }
        }
    }
}
